class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        //递归结束条件
        if(root == p || root == q) {
            return root;
        }
        //遍历左树
        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        //遍历右树
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
        //左不为空，右也不为空，根节点就是公共祖先
        if(leftTree != null && rightTree != null) {
            return root;
        } else if (leftTree != null) {
            //左不为空，右为空，那么左就是公共祖先
            return leftTree;
        } else {
            //左为空，右不为空，右就是公共祖先
            return rightTree;
        }


    }
}